/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    	if(pListHead == nullptr || k == 0)
    		return nullptr;
    	ListNode *end = pListHead;
    	while(k>1 && end != nullptr)
    	{
    		end = end->next;
    		--k;
    	}
    	if(end == nullptr)
    		return nullptr;
    	while(end->next)
    	{
    		end = end ->next;
    		pListHead = pListHead->next;
    	}
    	return pListHead;
    }
};


/*输入一个链表，反转链表后，输出链表的所有元素。
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
    	if(pHead == nullptr)
    		return nullptr;
    	ListNode*pre,*cur;
    	pre = pHead;
    	cur = pre->next;
    	pre->next = nullptr;
    	while(cur != nullptr)
    	{
    		pHead = cur->next;
    		cur->next = pre;
    		pre = cur;
    		cur = pHead;
    	}
    	return pre;
    }
};


/*输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode *temp = new ListNode(0);
        ListNode *head = temp;
        while(pHead1 != nullptr && pHead2 != nullptr)
        {
        	if(pHead2->val > pHead1->val)
        	{
        		temp->next = pHead1;
        		temp = temp->next;
        		pHead1 = pHead1->next;
        	}
        	else
        	{
        		temp->next = pHead2;
        		temp = temp->next;
        		pHead2 = pHead2 ->next;
        	}
        }
        if(pHead1!=nullptr)
        {
        	temp->next = pHead1;
        }
        if(pHead2!=nullptr)
        {
        	temp->next = pHead2;
        }
        return head->next;
    }
};